# 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
#
#  此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
#
#  注意:
# 不能使用代码库中的排序函数来解决这道题。
#
#  示例:
#
#  输入: [2,0,2,1,1,0]
# 输出: [0,0,1,1,2,2]
#
#  进阶：
#
#
#  一个直观的解决方案是使用计数排序的两趟扫描算法。
#  首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
#  你能想出一个仅使用常数空间的一趟扫描算法吗？
#
#  Related Topics 排序 数组 双指针
#  👍 567 👎 0

# todo 一趟遍历
# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # 思想很简单，就是占位，然后出现
        r, w, b = -1, -1, -1
        for i in range(0, len(nums)):
            if nums[i] == 0:
                nums[b + 1] = 2
                nums[w + 1] = 1
                nums[r + 1] = 0

                r += 1
                w += 1
                b += 1

            elif nums[i] == 1:
                nums[b + 1] = 2
                nums[w + 1] = 1
                w += 1
                b += 1

            elif nums[i] == 2:
                # 最后只有 白色，直接在当前白色的位置后面添加一个白色
                nums[b + 1] = 2
                b += 1





# leetcode submit region end(Prohibit modification and deletion)

arr = [2, 0, 2, 1, 1, 0]
Solution().sortColors(arr)
print(arr)
